#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/12/9 11:31|11:31
# @Author  : yangdingyi
# @File    : 合并两个有序链表
# @Software: PyCharm

from typing import List


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 and not l2:
            return l1
        elif not l1:
            return l2
        elif not l2:
            return l1
        else:
            if l1.val <= l2.val:
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1, l2.next)
                return l2


def make_list(data: List[int]) -> ListNode:
    root, p = None, None

    for i, n in enumerate(data):
        q = ListNode(n)
        if not root:
            root = q
            p = root
        else:
            p.next = q
            p = p.next
    return root


def display(root: ListNode) -> None:
    ans = []
    while root:
        ans.append(str(root.val))
        root = root.next
    print('->'.join(ans))


solve = Solution()
l1_arr = [1, 2, 4]
l1 = make_list(l1_arr)
l2_arr = [1, 3, 4]
l2 = make_list(l2_arr)

display(l1)
display(l2)

display(solve.mergeTwoLists(l1, l2))

